/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/combination-sum-ii
   @Language: C++
   @Datetime: 16-02-09 05:45
   */

class Solution {
	void getsum2(vector<int> &num,int tar,int pos
			,vector<vector<int> > &vs,vector<int> &v){
		if (tar==0){
			vs.push_back(v);
			return;
		}
		for (int i=pos; i<num.size() && num[i]<=tar; ++i){
			// skip duplication
			if (i!=pos && num[i]==num[i-1]) continue;
			v.push_back(num[i]);
			// each element can be used once
			getsum2(num,tar-num[i],i+1,vs,v);
			v.pop_back();
		}
	}

public:
	/**
	 * @param num: Given the candidate numbers
	 * @param target: Given the target number
	 * @return: All the combinations that sum to target
	 * Tip: each element can be used once,
	 *      and the result sets must have unique set
	 */
	vector<vector<int> > combinationSum2(vector<int> &num, int tar) {
		// write your code here
		vector<vector<int> > vs;
		vector<int> v;
		sort(num.begin(),num.end());
		getsum2(num,tar,0,vs,v);
		return vs;
	}
};
